#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod=1e9+7;

ll read(){
    char c;ll r;bool f=0;
    for(c=getchar();c>'9'||c<'0';c=getchar()) if(c=='-') f=1;
    for(r=0;c>='0'&&c<='9';c=getchar()) r=r*10+c-'0';
    if(f) return -r;
    else return r;
}

void print(const ll &x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

ll f[70][2];
inline ll solveNum(ll x){
    //if(x<=0) return 0;if(x==1) return 1;
    int lg=62;
    ll ans=0;
    for(ll mask=1ll<<61;mask;mask>>=1,lg--){
        if(mask&x){
            ans+=f[lg-1][1]+f[lg-1][0];
            if(x&(mask<<1)) break;
        }
    }
    return ans-1;
}

inline int add(const int &x,const int &y){ll $=x;return ($+y)%mod;}
inline int mul(const int &x,const int &y){ll $=x;return ($*y)%mod;}
struct Matrix{
    int $[2][2];

    inline void clear(){memset($,0,sizeof $);}
    const int* operator [] (const int &_) const {return $[_];}
    int* operator [] (const int &_) {return $[_];}
    const Matrix operator * (const Matrix &_) const{
        Matrix $$;
        $$.clear();
        for(int i=0;i<2;i++)
            for(int k=0;k<2;k++){
                if(!$[i][k]) continue;
                for(int j=0;j<2;j++)
                    $$[i][j]=add($$[i][j],mul($[i][k],_[k][j]));
            }
        return $$;
    }
};

template <typename T>
inline T qpow(T unit,T base,ll exp){
    while(exp){
        if(exp&1) unit=unit*base;
        base=base*base;
        exp>>=1;
    }
    return unit;
}

Matrix unit,init,rate;
inline int solveMat(ll x){
    Matrix ret=init*qpow(unit,rate,x);
    return add(ret[0][0],ret[0][1]);
}

int main(){
    f[0][0]=1;
    for(int i=1;i<70;i++) f[i][1]=f[i-1][0],f[i][0]=f[i-1][1]+f[i-1][0];
    //for(int i=1;i<=5;i++) printf("f[%d]: %I64d %I64d\n",i,f[i][0],f[i][1]);

    unit.clear();init.clear();rate.clear();
    unit[0][0]=unit[1][1]=1;init[0][0]=1;rate[0][0]=rate[0][1]=rate[1][0]=1;

    int T;
    T=read();
    while(T--){
        ll n;
        n=read();
        print(solveNum(n+1));putchar('\n');
        print(solveMat(n));putchar('\n');
    }

    return 0;
}
